//被围绕的区域
class Solution {
public:

    int m , n;
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    void dfs(vector<vector<char>>& board,int row , int col)
    {
        board[row][col] = '.';
        for(int i = 0 ; i < 4 ; ++i)
        {
            int x = col + dx[i] , y = row + dy[i];
            if(x >= 0 && y >= 0 && x < m && y < n && board[y][x] == 'O')
            {
                dfs(board,y,x);
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        //先处理边界情况
        m = board[0].size() , n = board.size();
        for(int i = 0 ; i < m ; ++i)
        {
            if(board[0][i] == 'O')
            {
                dfs(board,0,i);
            }
            if(board[n-1][i] == 'O')
            {
                dfs(board,n-1,i);
            }
        }
        for(int i = 0 ; i < n ; ++i)
        {
            if(board[i][0] == 'O')
            {
                dfs(board,i,0);
            }
            if(board[i][m-1] == 'O')
            {
                dfs(board,i,m-1);
            }
        }
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                if(board[i][j] == '.') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
    }
};

//岛屿的最大面积
class Solution {
public:
    int n , m;
    bool check[301][301];
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int ret;
    void dfs(vector<vector<char>> &grid , int row , int col)
    {
        check[row][col] = true;
        for(int i = 0 ; i < 4 ; ++i)
        {
            int x = col + dx[i] , y = row + dy[i];
            if(x >= 0 && y >= 0 && x < m && y < n && grid[y][x] == '1' && check[y][x] == false)
            {
                dfs(grid,y,x);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        //找到一个位置，该位置上下左右均不可走，即为岛屿
        n = grid.size() , m = grid[0].size() , ret = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                if(check[i][j] == false && grid[i][j] == '1')
                {
                    //访问整个岛屿
                    ret++;
                    dfs(grid,i,j);
                }
            }
        }
        return ret;
    }
};

//岛屿数量
class Solution {
public:
    int n , m;
    bool check[301][301];
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int ret;
    void dfs(vector<vector<char>> &grid , int row , int col)
    {
        check[row][col] = true;
        for(int i = 0 ; i < 4 ; ++i)
        {
            int x = col + dx[i] , y = row + dy[i];
            if(x >= 0 && y >= 0 && x < m && y < n && grid[y][x] == '1' && check[y][x] == false)
            {
                dfs(grid,y,x);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        //找到一个位置，该位置上下左右均不可走，即为岛屿
        n = grid.size() , m = grid[0].size() , ret = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                if(check[i][j] == false && grid[i][j] == '1')
                {
                    //访问整个岛屿
                    ret++;
                    dfs(grid,i,j);
                }
            }
        }
        return ret;
    }
};

//图像渲染
class Solution {
public:
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int srColor , scColor , n , m;
    void dfs(vector<vector<int>>& image,int row , int col)
    {
        image[row][col] = scColor;
        for(int i = 0 ; i < 4 ; ++i)
        {
            int x = col + dx[i] , y = row + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n && image[y][x] == srColor && image[y][x] != scColor)
            {
                dfs(image,y,x);
            }
        }

    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        n = image.size() , m = image[0].size();
        srColor = image[sr][sc];
        scColor = color;
        dfs(image,sr,sc);
        return image;
    }
};

//不同路径Ⅲ
class Solution {
public:
    //记录0的个数
    int zero_num , n , m , start_row , start_col , ret;
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    bool check[21][21];
    void dfs(vector<vector<int>>& grid,int row,int col)
    {
        if(grid[row][col] == 2 && zero_num == 0)
        {
            ret++;
            return;
        }
        check[row][col] = true;
        for(int i = 0 ; i < 4 ; ++i)
        {
            int y = row+dy[i] , x = col+dx[i];
            if(y < n && y >= 0 && x < m && x >= 0 && (grid[y][x] == 0 || grid[y][x] == 2) && check[y][x] == false)
            {
                if(grid[y][x] == 0)--zero_num;
                dfs(grid,y,x);
                if(grid[y][x] == 0)++zero_num;
            }
        }
        check[row][col] = false;
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
        zero_num = 0 , n = grid.size() , m = grid[0].size() , start_row = 0 , start_col = 0  , ret = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                if(grid[i][j] == 0) zero_num++;
                else if(grid[i][j] == 1) start_row = i , start_col = j;
            }
        }
        dfs(grid,start_row,start_col);
        return ret;
    }
};

//黄金矿工
class Solution {
public:
    bool check[16][16];
    int m , n , path,max;
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    void dfs(vector<vector<int>>& grid,int row , int col)
    {
        path += grid[row][col];
        if(path > max) max = path;
        check[row][col] = true;
        for(int i = 0 ; i < 4 ; ++i)
        {
            int x = col + dx[i] , y = row + dy[i];
            if((y < n && y >= 0) && (x < m) && (x >= 0) && (grid[y][x] != 0) && (check[y][x] != true))
            {
                dfs(grid,y,x);
            }
        }
        check[row][col] = false;
        path -= grid[row][col];
    }
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid[0].size() , n = grid.size() , path = 0 , max = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                if(grid[i][j] != 0)
                {
                    dfs(grid,i,j);
                }
            }
        }
        return max;
    }
};

//单词搜索
class Solution {
public:
    bool check[10][10];
    bool dfs(vector<vector<char>>& board,int row,int col , int n , string word)
    {
        if(n == word.size()) return true;
        check[row][col] = true;
        if((col+1 < board[0].size() )&&(board[row][col+1] == word[n])&&(!check[row][col+1]))
        {
            if(dfs(board,row,col+1,n+1,word)) return true;
        }
        if((col-1 >= 0)&&(board[row][col-1] == word[n])&&(!check[row][col-1]))
        {
            if(dfs(board,row,col-1,n+1,word)) return true;
        }
        if((row+1 < board.size()) && (board[row+1][col] == word[n]) && (!check[row+1][col]))
        {
            if(dfs(board,row+1,col,n+1,word)) return true;
        }
        if((row-1 >= 0)&&(board[row-1][col] == word[n])&&(!check[row-1][col]))
        {
            if(dfs(board,row-1,col,n+1,word)) return true;
        }
        check[row][col] = false;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0 ; i < board.size() ; ++i)
        {
            for(int j = 0 ; j < board[0].size() ; ++j)
            {
                if(board[i][j] == word[0])
                {
                    if(dfs(board,i,j,1,word)) return true;
                }
            }
        }
        return false;
    }
};